//无头的双链表
public class MyLinkedList {
    static class ListNode{
        //三个域
        public int val;
        public ListNode prev;
        public ListNode next;

        public ListNode (int val){
            this.val=val;
        }
    }
        //标记双向链表的头
        public ListNode head;
        //标记双向链表的尾巴
        public ListNode tail;




       //头插法
       public void addFirst(int data){
           ListNode node=new ListNode(data);
           if(this.head==null){
               this.tail=node;
               this.head=node;
           }else{
               node.next=this.head;
               this.head.prev=node;
               this.head=node;

           }


       }
       //尾插法
       public void addLast(int data){
           ListNode node=new ListNode(data);
           if(this.head==null){
               this.head=node;
               this.tail=node;
           }else{
               tail.next=node;
               node.prev=tail;
               tail=node;
           }
       }
       // 任意位置插入,第一个数据节点为0号下标
       public void addIndex(int index,int data){
           //1.判断Index的合法性
           int length=size();
           if(index<0||index>length){
               return;
           }
           //2.判断特殊位置——>头插法 尾插法
           if(head==null){
               addFirst(data);
               return;
           }
           if(index==length){
               addLast(data);
               return;
           }
           // 3.中间位置插入 改动4个位置
           ListNode cur=findIndexListNode(index);
           ListNode node=new ListNode(data);
           node.next=cur;
           cur.prev.next=node;
           node.prev=cur.prev;
           cur.prev=node;
       }
       public ListNode findIndexListNode(int index){
           ListNode cur=head;
           while(index!=0){
               cur=cur.next;
               index--;
           }
           return cur;

       }
       // 查找是否包含关键字key是否在单链表当中
       public boolean contains(int key){
           ListNode cur=head;
           while(cur!=null){
               if(cur.val==key){
                   return true;
               }
           }
           return false;
       }
       // 删除第一次出现关键字为key的节点
       public void remove(int key){
           ListNode cur = head;
           while (cur != null) {
               if(cur.val == key) {
                   if(cur == head) {
                       head = head.next;
                       if(head != null) {
                           head.prev = null;
                       }else {
                           tail = null;
                       }
                   }else {
                       cur.prev.next = cur.next;
                       if(cur.next != null) {
                           cur.next.prev = cur.prev;
                       }else {
                           this.tail = cur.prev;
                       }
                   }
                   return;
               }
               cur = cur.next;
           }
       }
       // 删除所有值为key的节点
       public void removeAllKey(int key){
           ListNode cur = head;
           while (cur != null) {
               if(cur.val == key) {
                   if(cur == head) {
                       head = head.next;
                       if(head != null) {
                           head.prev = null;
                       }else {
                           tail = null;
                       }
                   }else {
                       cur.prev.next = cur.next;
                       if(cur.next != null) {
                           cur.next.prev = cur.prev;
                       }else {
                           this.tail = cur.prev;
                       }
                   }
               }
               cur = cur.next;
           }
       }
       // 得到单链表的长度
       public int size(){
           ListNode cur=this.head;
           int sum=0;
           while(cur.next!=null){
               sum++;
           }
           return sum;
       }
       public void display(){
           ListNode cur=head;
          while(cur.next!=null){
              System.out.print(cur.val+" ");
              cur=cur.next;
          }
       }
        public void clear(){
            ListNode cur=head;
            ListNode curNext=cur.next;
            while(cur!=null){
                head.next=null;
                head.prev=null;
                cur=curNext;
            }
            head=null;
            tail=null;
        }

}
